/*
    状压dp-下

    前置知识: 
    讲解003、讲解030、讲解031、讲解032、讲解033 - 位运算基础算法
    讲解043 - 根据数据量猜解法的技巧，天字第一号重要技巧
    讲解063 - 双向广搜
    讲解067 - 从递归入手二维动态规划
    讲解080 - 状压dp-上
    【必备】课程的动态规划大专题从讲解066开始，建议从头开始学习会比较系统

    上节课讲述了状压dp的原理和一些经典题目
    本节课继续讲述4个状压dp问题，以及重要技巧：如何在位状态上，枚举所有子集的状态（题目4）

    注意：
    轮廓线dp是状压dp中一类比较难的问题，【扩展】课程阶段讲述
    插头dp是轮廓线dp中一类更难的问题，在笔试、面试中几乎没有出现的可能，不会安排。比赛同学自行学习

    ================================================

    题目1
    每个人戴不同帽子的方案数
    总共有 n 个人和 40 种不同的帽子，帽子编号从 1 到 40
    给你一个整数列表的列表 hats ，其中 hats[i] 是第 i 个人所有喜欢帽子的列表
    请你给每个人安排一顶他喜欢的帽子，确保每个人戴的帽子跟别人都不一样，并返回方案数
    由于答案可能很大，请返回它对10^9+7取余后的结果
    测试链接 : https://leetcode.cn/problems/number-of-ways-to-wear-different-hats-to-each-other

    ================================================

    题目2
    最优账单平衡
    给你一个表示交易的数组 transactions
    其中 transactions[i] = [fromi, toi, amounti]
    表示 ID = fromi 的人给 ID = toi 的人共计 amounti
    请你计算并返回还清所有债务的最小交易笔数
    测试链接 : https://leetcode.cn/problems/optimal-account-balancing/

    注意：
    大部分题解的时间复杂度O(3^n)，这不是最优解，不再讲述
    最优解的时间复杂度O(2^n * n)，也就是课上讲的解法

    ================================================

    题目3
    好子集的数目
    给你一个整数数组 nums，好子集的定义如下：
    nums的某个子集，所有元素的乘积可以表示为一个或多个互不相同质数的乘积
    比如nums = [1, 2, 3, 4]
    [2, 3]，[1, 2, 3]，[1, 3] 是好子集
    乘积分别为6=2*3，6=2*3，3=3
    [1, 4]和[4]不是好子集，因为乘积分别为4=2*2和4=2*2
    请你返回nums中不同的好子集的数目对10^9+7取余的结果
    如果两个子集拥有的下标不同，那么它们被视为不同的子集
    测试链接 : https://leetcode.cn/problems/the-number-of-good-subsets/

    ================================================

    题目4
    分配重复整数
    给你一个长度为n的整数数组nums，这个数组中至多有50个不同的值
    同时你有m个顾客的订单quantity，其中整数quantity[i]是第i位顾客订单的数目
    请你判断是否能将nums中的整数分配给这些顾客，且满足：
    第i位顾客恰好有quantity[i]个整数、第i位顾客拿到的整数都是相同的
    每位顾客都要满足上述两个要求，返回是否能都满足
    测试链接 : https://leetcode.cn/problems/distribute-repeating-integers/

    不能用贪心的例子 : nums = [1,1,2,2,1]、quantity = [2,2,1]

    j枚举了status的所有子集状态，建议直接记住
    for (int j = status; j > 0; j = (j - 1) & status) { .. }

    ================================================

    题目4的时间复杂度分析

    时间复杂度 O(n * 3的m次方)，n不用说了，可变参数index的变化范围，那后面的3的m次方怎么来的？
    元素个数为m的集合:
    其中挑选0个元素组成子集，数量为C(m,0)，这个子集去枚举它的所有子集，枚举代价2的0次方
    其中挑选1个元素组成子集，数量为C(m,1)，这个子集去枚举它的所有子集，枚举代价2的1次方
    . . .
    其中挑选k个元素组成子集，数量为C(m,k)，这个子集去枚举它的所有子集，枚举代价2的k次方
    . . .
    其中挑选m个元素组成子集，数量为C(m,m)，这个子集去枚举它的所有子集，枚举代价2的m次方
    把上面都加起来，总和 =
                    
    3的m次方 = (1+2)的m次方，把(1+2)的m次方根据二项式定理展开，就能得到上面的式子

    Wiki 百科二项式定理：https://zh.wikipedia.org/zh-hans/%E4%BA%8C%E9%A1%B9%E5%BC%8F%E5%AE%9A%E7%90%86

*/